/*
 * @lc app=leetcode.cn id=222 lang=typescript
 *
 * [222] 完全二叉树的节点个数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

//  思路：递归
//  节点数 = 左子树的数量 + 右子树的数量 + 根节点
//  根据满二叉树的特性来降低复杂度
//  因为一定有一棵树触发 hl === hr 条件

//  参考：https://labuladong.github.io/algo/2/19/32/

//  复杂度： O(logn * logn) O(1)

function countNodes(root: TreeNode | null): number {
    // base case
    if (!root) return 0
    let left: TreeNode | null = root, right: TreeNode | null = root
    let hl = 0, hr = 0
    // 计算高度
    while (left) {
        left = left.left
        hl++
    }
    while (right) {
        right = right.right
        hr++
    }
    if (hl === hr) return Math.pow(2, hl) - 1

    return countNodes(root.left) + countNodes(root.right) + 1

};
// @lc code=end

import { TreeNode } from "./type"
const root = TreeNode.buildTree([1, 2, 3, 4, 5, 6])
console.log(countNodes(root))
